#include<iostream>
#include<stack>
#include<vector>
using namespace std;

stack<int> stk;
vector<vector<int>> res;
vector<int> path;

bool dfs(vector<int>& putIn, int index, vector<int>& takeOut, int outdex){
    int n = putIn.size();
    // way1 直接push
    if(index < n){
        stk.push(putIn[index]);
        if(dfs(putIn, index+1, takeOut, outdex)) return true;
        stk.pop();
    }
    // way2 从stack中弹出
    if(stk.size()){
        int top = stk.top();
        if(top != takeOut[outdex]) return false;
        path.push_back(top);
        stk.pop();
        if(dfs(putIn, index, takeOut, outdex+1)) return true;
        stk.push(top);
    }
    if(index == n && stk.empty()){
        return true;
    }
    return false;
}

void print(const vector<vector<int>>& res) {
    for (const auto& row : res) {
        for (const auto& num : row) {
            cout << num << " ";
        }
        cout << endl;
    }
}

int main(){
    vector<int> nums = {1, 2, 3, 4};
    // stack_sort(nums, 0);
    // print(res);
    vector<int> takenIn = {1, 2, 3};
    vector<int> takeOut = {3, 2, 1};
    bool ans = dfs(takenIn, 0, takeOut, 0);
}